package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1365 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int[] smallerNumbersThanCurrent(int[] nums) {
            TreeMap<Integer, Integer> orderMap = new TreeMap<>(Collections.reverseOrder());
            LinkedHashMap<Integer, List<Integer>> posMap = new LinkedHashMap<>();
            for (int i = 0; i < nums.length; i++) {
                orderMap.put(nums[i], orderMap.getOrDefault(nums[i], 0) + 1);
                if (posMap.containsKey(nums[i])) posMap.get(nums[i]).add(i);
                else {
                    List<Integer> posList = new LinkedList<>();
                    posList.add(i);
                    posMap.put(nums[i], posList);
                }
            }

            int[] res = new int[nums.length];
            int alreadyCount = 0;
            for (Integer key : orderMap.keySet()) {
                alreadyCount += orderMap.get(key);
                for (Integer pos : posMap.get(key)) {
                    res[pos] = nums.length - alreadyCount;
                }
            }

            return res;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[8,1,2,2,3]");
        System.out.println(solution.smallerNumbersThanCurrent(arr));
    }

    public static void main(String[] args) throws Exception {
        LC1365 an = new LC1365();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
